class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
    	if(sequence.size() == 0)
    		return false;
    	return subTreeVerify(sequence,0,sequence.size()-1);
    }

    bool subTreeVerify(const vector<int> &sequence,int begin,int end)
    {
    	int bg = begin,ed = end - 1;
    	if(end - begin < 2)
    		return true;
    	int target = sequence[end--];
		while(sequence[begin] < target)
			++begin;
    	while(sequence[end] > target)
    		--end;
    	if(end + 1 == begin)
    		return subTreeVerify(sequence,bg,end)&&subTreeVerify(sequence,begin,ed);
    	else
    		return false;
    }
};